\section{产生数(P1037)}

\subsection{题目描述}

给出一个整数$n(n<10^{30})$和k个变换规则$(k \leq 15)$。

规则：

一位数可变换成另一个一位数：

规则的右部不能为零。

例如：n=234。有规则（k=2）：

$2->5$

$3->6$

上面的整数234经过变换后可能产生出的整数为（包括原数）:

234

534

264

564

共4种不同的产生数

问题：

给出一个整数 n 和k 个规则。

求出：

经过任意次的变换（0次或多次），能产生出多少个不同整数。

仅要求输出个数。

\subsection{输入}
键盘输入，格式为：

n\quad k \\
x1\quad y1 \\
x2\quad y2 \\
... \\

xn\quad yn

\subsection{输出}
屏幕输出，格式为：

1个整数（满足条件的个数）：

\subsection{样例}
\textbf{输入样例}
\begin{lstlisting}
234 2
2 5
3 6
\end{lstlisting}
\textbf{输出样例}
\begin{lstlisting}
4
\end{lstlisting}

\subsection{提示}

\subsection{分析}
这个题的基本思路是：检查每个位有几种可能，然后再把所有这些位的可能的数量乘起来。这个题的一个陷阱是：有些用例的结果超出了
long long类型的范围，因此必须用大数模拟。

检查某位有几种可能的时候，使用了一个目标集合(tgt),用某位是否为1来表示集合是否包含对应的数字。
例如：这位包含0，则把tgt的第0位置1。

首先把这位原来的数字加入这个tgt集合，然后循环用tgt集合中的数字来匹配规则的source-char，如果匹配，则把对应的target-char
加入到tgt集合中（如果已经在集合中，则跳过此步骤）。如此循环，知道所有可能的数字都加入了tgt集合。此时tgt集合中包含的数字的
数量，就是这一位的个数。

\subsection{代码}
\begin{lstlisting}
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <unistd.h>

using namespace std; 

#define  N 32
#define  K 16

char num[N]; 
char rule[K][2]; 
int k; 

int bit_nr[N]; 

void dfs(int pos)
{
	char c; 
	int found, tgt=0; 
	char *p = &num[pos]; 
	int res = 1; 
	if (*p=='\0') {
		bit_nr[pos] = 1; 
		return; 
	}
	// tgt is the set of number which this bit could be
	tgt |= (1<<(*p-'0')); 
	do {
		found = 0; 
		for (int j=0; j<10; j++) { 
			// if this number is not reachable, skip it.
			if ((tgt&(1<<j))==0) {
				continue; 
			}
			c = j+'0'; 
			for (int i=0; i<k; i++) {
				// if the source-char of the rule is not the target, skip it
				if (rule[i][0]!=c)
					continue; 
				// if the source-char of the rule is already in the tgt, skip it
				if (tgt & (1<<(rule[i][1]-'0')))
					continue; 
				// found a new target-char could be reachable
				found = 1; 
				tgt |= 1<<(rule[i][1]-'0'); 
				res ++; 
			}
		}
	} while(found); 
	bit_nr[pos] = res; 
	dfs(pos+1); 
}


#define NB 100
void out_result(void)
{
	int big_int[NB], i, j;
	int last_bit = 0;  
	
	// don't forget initialize the array
	for (i=0; i<NB; i++) 
		big_int[i] = 0; 

	big_int[last_bit] = 1; 
	for (j=0; num[j]; j++) {
		for (i=0; i<=last_bit; i++) {
			big_int[i] *= bit_nr[j]; 
		}
		for (i=0; i<=last_bit; i++) {
			int a, b; 
			a = big_int[i]%10; 
			b = big_int[i]/10; 
			big_int[i] = a; 
			big_int[i+1] += b; 
		}
		if (big_int[i]!=0) {
			last_bit = i;
		} 
	}
	
	for (i=last_bit; i>=0; i--) {
		printf("%d", big_int[i]); 
	}
	printf("\n"); 
}

int main()
{
	int o, t; 
	scanf("%s %d", num, &k); 
	for (int i=0; i<k; i++) {
		scanf("%d %d", &o, &t); 
		rule[i][0] = '0' + o; 
		rule[i][1] = '0' + t; 
	}
	dfs(0); 
	out_result(); 
	return 0; 
}
\end{lstlisting}


